package com.mlh.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 缪林辉
 * @date 2024/8/16 12:32
 * @DESCRIPTION
 */
//给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
// 子数组是数组中元素的连续非空序列。
// 输入：nums = [1,1,1], k = 2
// 输出：2
public class 和为K的子数组 {
    //这题题解看 灵茶山艾府 的
    //该解法利用到前缀和 还有 两数之和的解法思想
    //为什么要用前缀和，用当前和貌似也没什么问题
    //用当前和的话  没办法把任意子数组都表示成两个前缀和的差
    // 比如 0-right子数组 如果是当前和的话必须特判左边界为0时
    //如果使用前缀和 只需要将prefixSum[right+1]-prefixSum[0]即可
    public int method1(int[] nums, int k) {
        //第一次遍历计算前缀和
        int len=nums.length,res=0;
        int[] prefixSum=new int[len+1];
        //注意 前缀和prefixSum[0]=0 想把任意子数组都表示成两个前缀和的差，必须添加 s[0]=0
        for (int i = 1; i <=len; i++) {
            prefixSum[i]=prefixSum[i-1]+nums[i-1];
        }
        Map<Integer,Integer>map=new HashMap<>();
        for (int i = 0; i <=len; i++) {
            res+=map.getOrDefault(prefixSum[i]-k,0);//查找map中有没有key为prefixSum[i]-k 的前缀和
            //把当前前缀和加入到map中
            //Map 接口的 merge 方法提供了一种便捷的方式来将键（key）和值（value）合并到 Map 中。
            // 如果键已经存在，merge 方法可以将旧值与新值通过给定的函数合并；如果键不存在，它将简单地将键值对添加到 Map 中。
            map.merge(prefixSum[i],1,Integer::sum);
        }
        return res;
    }

    public int practice(int[] nums, int k) {
        int len=nums.length;
        int []prefixSum=new int[len+1];
        for (int i = 1; i <prefixSum.length; i++) {
            prefixSum[i]=prefixSum[i-1]+nums[i-1];
        }
        HashMap<Integer,Integer>map=new HashMap<>();
        int res=0;
        for (int i = 0; i < prefixSum.length; i++) {
            if(map.containsKey(prefixSum[i]-k)){
                res+=map.get(prefixSum[i]-k);
            }
            map.merge(prefixSum[i],1,Integer::sum);
        }
        return res;
    }
}
